package P003;

import org.junit.Test;

import java.util.HashMap;

/**
 * @Author DJ同学
 * @Date 2021/2/7 16:53
 * @Version 1.0
 * @Name 无重复字符的最长子串
 * @Priblem https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @Tips 滑动窗口
 * 适合输入是一个数组或者字符串，求解的结果是具有某种特质的子数组或者子字符串
 *
 * 当不满足条件时，拓展右边界，当满足条件时，缩短左边界，最后得到一个解并暂存
 * 循环第一步，又得到一个解，将其与第一个解相对比，得到最优解并暂存，以此类推
 */

public class Solution {
    @Test
    public void test01(){
        //java的string中没有s[0] 使用s.charAt(0)
//        String s = "abcabcbb";
        String s = "abcdefcdf";

        System.out.println(lengthOfLongestSubstring(s));
    }


    public int lengthOfLongestSubstring(String s) {
        //处理异常输入
        if(s==null||s.length()==0){
            return 0;
        }
        int maxLen = 0;

        //定义窗口边界
        int begin = 0;
        int end = 0;

        HashMap<Character,Integer> map = new HashMap<>();
        while(end<s.length()){

            //缩窗口 满足条件（存在了一个无重复串）
            if(map.containsKey(s.charAt(end))&&map.get(s.charAt(end))>=begin){
               while(map.containsKey(s.charAt(end))&&map.get(s.charAt(end))>=begin){
                   maxLen = Math.max(maxLen,end-begin);
                   begin =  map.get(s.charAt(end)) + 1;
               }
               //注意：这边不使用continue;虽然不影响，但是使用continue,会执行2遍map.put
            }
            map.put(s.charAt(end),end);
            //扩窗口 不满条件
            end++;
        }
        maxLen = Math.max(maxLen,end-begin);
        return maxLen;
    }
}
